package algorithms.leaning.class26;

import common.util.MyUtil;

/**
 * 斐波那契数列矩阵乘法方式的实现
 * f(n) = f(n-1) + f(n-2)，其中：f(1) = f(2) = 1
 *
 * @author guichang
 * @date 2021/6/28
 */

@SuppressWarnings("all")
public class Code2_严格数列矩阵乘法_斐波拉契 {

    public static void main(String[] args) {
        for (int i = 1; i <= 30; i++) {
            MyUtil.printf("f1: {}-{}, f2: {}-{}", i, f1(i), i, f2(i));
        }
    }

    /**
     * 遍历一次得到
     * 时间复杂度：O(N)
     * f(n) = f(n-1) + f(n-2)
     */
    public static int f1(int N) {
        if (N <= 0) {
            return -1;
        }
        if (N <= 2) {
            return 1;
        }
        int f1 = 1, f2 = 1;
        for (int i = 3; i <= N; i++) {
            int tmp = f2;
            f2 = f1 + f2;
            f1 = tmp;
        }
        return f2;
    }

    /**
     * 利用矩阵乘法得到
     * 时间复杂度：O(logN)
     */
    public static int f2(int N) {
        if (N <= 0) {
            return -1;
        }
        if (N <= 2) {
            return 1;
        }
        // 二阶矩阵
        int[][] matrix = {
                {1, 1},
                {1, 0}
        };
        int[][] mult = powerMatrix(matrix, N - 2);
        return mult[0][0] + mult[1][0];
    }

    /**
     * 矩阵matrix的n次幂
     * 时间复杂度：O(logN)
     */
    private static int[][] powerMatrix(int[][] matrix, int n) {
        // 单位矩阵，斜对角上是1，其他全是0
        int N = matrix.length;
        int[][] res = new int[N][N];
        for (int i = 0; i < N; i++) {
            res[i][i] = 1;
        }
        // 快速求出某个数的n次方
        int[][] t = matrix;
        for (; n != 0; n >>= 1) {
            // n的最后边是1的话就要乘当前的t了
            if ((n & 1) == 1) {
                res = multMatrix(res, t);
            }
            // t始终乘自己
            t = multMatrix(t, t);
        }
        return res;
    }

    /**
     * 两矩阵相乘
     */
    public static int[][] multMatrix(int[][] m1, int[][] m2) {
        int row = m1.length; //结果矩阵的行数
        int col = m2[0].length; // 结果矩阵的列数
        int[][] res = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }


}